LFU Cache란?
cache 알고리즘에는 크게 3가지가 있습니다.
- FIFO : First in First Out - 제일 먼저 들어온 캐시를 교체
- LRU : Least Recently Used - 가장 오랫동안 사용되지 않은 캐시 교체
- LFU : Least Frequently Used - 사용 횟수가 가장 적은 캐시 교체
LFU (LEast Frequently Used)는 가장 참조 횟수가 적은 페이지를 교체하는 알고리즘 입니다.
LFU는 다음과 같이 Queue를 이용해서 구현됩니다. 저장되는 모든 데이터는 count라는 값을 가지게되며, 새로운 데이터가 들어올때 Queue에 저장된 값들중에서 가장 count값이 작은 값을 삭제하고 새로운 값을 저장합니다.
C++ 코드로 보기
#include <iostream>
using namespace std;
class LFUCache {
LFUCache(int capacity) {
}
int get(int key) {
}
void put(int key, int value) {
}
};
int main() {
LFUCache lfu = new LFUCache(2);
lfu.put(1, 1);
lfu.put(2, 2);
lfu.get(1);
lfu.put(3, 3);
lfu.get(2);
lfu.get(3);
lfu.put(4, 4);
lfu.get(1);
lfu.get(3);
lfu.get(4);
return 0;
}